#include <stdio.h>
#include <string.h>

int ans[16000];

void predo()
{
    int a, b, c;
    int n=15000, i;
   // freopen("check_b.txt","w",stdout);
    a = 1; b=1;
    ans[0] = 0; ans[1] = 1; ans[2] = 1;
    c = a+b;    
    for (i=3; i<=n; ++i)
    {
        c = c%10000;
        ans[i] = c;
        a = b; b = c;
        c = a+b;
    }    
  /*  for (i=1; i<=n;++i)
        printf("%d\n", ans[i]); */
}    


int main()
{
    predo();    
    int a;
    while (scanf("%d", &a), a!=-1)
    {
        a=a%15000;
//        if (a==0) a=15000;
        printf("%d\n", ans[a]);
    }    
    
    return 0;
}    
